package com.jz.algorithm.Stack;

import java.util.*;

/**
 * @Classname StackSeries
 * @Description TODO
 * @Date 2021/10/20 17:31
 * @Author 
 * @Version 
 */
public class StackSeries {
    private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
        put('{','}'); put('[',']'); put('(',')'); put('?','?');
    }};


    /**
     * @Methodname 
     * @Description TODO
     * @Date 2021/10/20 17:30
     * @Author Jz
     * @Return 
     * @Param 
     */
    public void appendTail(int value) {

    }

    public int deleteHead() {

        return 0;
    }

/**
 * @Methodname isValid
 * @Description 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Date 2021-11-26 11:28
 * @Author Jz
 * @Return 
 * @Param 
 */
    public static boolean isValid(String s) {



        if(s.length() > 0 && !map.containsKey(s.charAt(0))) {
            return false;
        }
        LinkedList<Character> stack = new LinkedList<Character>() {{ add('?'); }};
        for(Character c : s.toCharArray()){
            if(map.containsKey(c)) {
                stack.addLast(c);
            } else if(!map.get(stack.removeLast()).equals(c)) {
                return false;
            }
        }
        return stack.size() == 1;


    }
  
    public static boolean isValid1(String s){

        LinkedList<Character> linkedList=new LinkedList<Character>(){{ add('?');}};
        if (!map.containsKey(s.charAt(0))){
            return false;
        }
        for (char c : s.toCharArray()) {

            if (map.containsKey(c)){
                linkedList.addLast(c);
            }
            else if(!map.get(linkedList.removeLast()).equals(c)){
                return  false;
            }
        }
        return linkedList.size()==1;



    }
    /**
     * @Methodname removeDuplicates
     * @Description 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一
     * @Date 2021-11-26 14:14
     * @Author Jz
     * @Return 删除重复项的后的字符串
     * @Param  原始字符串s
     */
    public static String removeDuplicates(String s) {

        //abbaca
        LinkedList<Character> linkedList = new LinkedList<Character>(){{add('?');}};
        for (char c : s.toCharArray()) {

            if (linkedList.getLast() == c) {
                linkedList.removeLast();
            }
            else {
                linkedList.addLast(c);
            }
        }
        StringBuilder stringBuilder=new StringBuilder();
       linkedList.forEach(s1->stringBuilder.append(s1));
       return stringBuilder.toString().substring(1);


    }


    /**
     * @methodname evalRPN
     * @description 逆波兰表达式求值
     * @date 2021-12-3 9:47
     * @author Jz
     * @return 最后的求值
     * @param tokens 一个数组值
     */
    public  static int evalRPN(String[] tokens) {

        LinkedList<Integer> integers = new LinkedList<>();

        for (String token : tokens) {

            try {
                Integer integer = Integer.valueOf(token);

                integers.addLast(integer);
            }

           catch (Exception e) {
                Integer integer1 = integers.removeLast();
                Integer integer2 = integers.removeLast();
                Integer integer3 =calculate(integer2,integer1,token);
                integers.addLast(integer3);
            }
        }
        return  integers.removeLast();


    }
    
    /**
     * @methodname maxSlidingWindow
     * @description 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     *
     * 返回滑动窗口中的最大值
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @date 2021-12-3 15:36
     * @author Jz
     * @return 
     * @param 
     */

    public  static  int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> objects = new LinkedList<>();


        int[] ints = new int[nums.length + 1 - k];
        int max = nums[0];


        if (k == 1) {
            return nums;
        }
        if (k >= nums.length) {
            Arrays.sort(nums);
            ints[0] = nums[nums.length - 1];
            return ints;
        }
        int i = 0;
        int k1=0;
        for (int i1 = 0; i1 < nums.length; i1++) {

            while(!objects.isEmpty()&&nums[i1]>nums[objects.getLast().intValue()]){
                objects.removeLast();
            }
            objects.addLast(i1);
            if (i1==k-1){
                ints[i++]=nums[objects.getFirst()];
            }
            else if (i1>=k){
                if (objects.contains(Integer.valueOf(k1))) {
                    objects.remove(Integer.valueOf(k1));

                }
                ints[i++]=nums[objects.getFirst().intValue()];
                k1++;

            }

        }




       return ints;

    }




    

    private static Integer calculate(Integer integer1, Integer integer2, String token) {
        if (token.equals("+")){
            return  integer1+integer2;
        }
        else if (token.equals("-")){
            return integer1-integer2;
        }
        else if (token.equals("*")){
             return  integer1*integer2;
        }else {
               return  integer1/integer2;
        }
    }

    public static void main(String[] args) {
       // String s="(){}}{";
        //System.out.println(removeDuplicates("abbaca"));
        int [] tokens={7,2,4};
        int[] ints = maxSlidingWindow(tokens, 2);

        // isValid1(s);
    }

}
